package _220327;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/**
 * @author ShadowLim
 * @create 2022-03-27-9:44
 */
public class 迷宫与陷阱 {
    static int n, k;
    static int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    static char[][] map;
    static boolean[][][] vis;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(), k = scanner.nextInt();
        map = new char[n + 2][n + 2];
        vis = new boolean[n + 2][n + 2][11];
        String str = scanner.nextLine();
        for (int i = 1; i <= n; i++) {
            str = scanner.nextLine();
            for (int j = 0; j < str.length(); j++) {
                map[i][j + 1] = str.charAt(j);
            }
        }

        int ans = -1;
        Queue<Node> q = new LinkedList<>();
        q.offer(map[1][1] == '.' ? new Node(1, 1, 0, 0) : new Node(1, 1, 0, k));
        if (map[1][1] == '.') {
            vis[1][1][0] = true;
        } else {
            vis[1][1][k] = true;
        }
        while (!q.isEmpty()) {
            Node node = q.poll();
            if (node.x == n && node.y == n) {
                ans = node.step;
                break;
            }
            for (int i = 0; i < 4; i++) {
                int nx = node.x + dirs[i][0], ny = node.y + dirs[i][1];
                // 非墙壁且不越界
                if (map[nx][ny] != '#' && nx >= 1 && nx <= n && ny >= 1 && ny <= n) {
                    if (map[nx][ny] == 'X' && node.invincible > 0 && vis[nx][ny][node.invincible - 1] == false) {
                        vis[nx][ny][node.invincible - 1] = true;
                        q.offer(new Node(nx, ny, node.step + 1, node.invincible - 1));
                    } else if (map[nx][ny] == '%' && !vis[nx][ny][k]) { // 无敌状态
                        vis[nx][ny][k] = true;
                        q.offer(new Node(nx, ny, node.step + 1, k));
                    } else if (map[nx][ny] == '.' && node.invincible == 0 && vis[nx][ny][0] == false) {
                        vis[nx][ny][0] = true;
                        q.offer(new Node(nx, ny, node.step + 1, 0));
                    } else if (map[nx][ny] == '.' && node.invincible > 0 && vis[nx][ny][node.invincible-1] == false) {
                        vis[nx][ny][node.invincible - 1] = true;
                        q.offer(new Node(nx, ny, node.step + 1, node.invincible - 1));
                    }
                }
            }
        }
        System.out.println(ans);
    }
}

class Node {
    int x, y, step, invincible;

    public Node(int x, int y, int step, int invincible) {
        this.x = x;
        this.y = y;
        this.step = step;
        this.invincible = invincible;   // 无敌状态持续步数
    }
}
